/* NoX (NoC Simulator)
 *
 * Dept. of Computer Science & Engineering, Pennsylvania State University.
 * All Rights Reserved.
 *  
 * 1. License     
 * NoX is distributed free of charge for academic, educational, noncommercial 
 * research purposes as long as this notice in its entirety is preserved in
 * every file included in this package.
 * All commercial use of this program requires separate licence. Contact the
 * author for details.
 * 
 * 2. All the publications that used the simulation results generated by the 
 * NoX should notify the author of the publication information and put 
 * following reference.
 *
 *  http://www.cse.psu.edu/~dpark/nox/
 * 
 * 3. Modification of the source code is permitted and encouraged as long as 
 * it follows the terms described in this copyright notice.
 *
 * 4. The author is not responsible for any problems caused by possible errors
 * of the NoX package. Therefore, users should verify the simulation result
 * before using it in their publication.
 *
 * Dept. of Computer Science & Engineering, Pennsylvania State University.
 * Contact: dpark@cse.psu.edu 
 * 
 * 6. If problems are found with the NoX package, please send an email to the
 * author for discussion and correction.

 */

/* Update History
 *
 *
 */

/* ROUTE_DETERMINISTIC.C - Implements the deterministic routing algorithm */


#include <math.h>
#include <stdlib.h>
#include "main.h"
#include "router.h"
#include "router_common.h"
#include "shared.h"
#include "flit.h"

bool is_neighbor(int cn, int dn, int *cpc)
{
  int pc=0;
  NUM_PC = router_info[cn].num_pc;
  NUM_NIC_PC = router_info[cn].num_nic_pc;

  for(pc=0; pc < NUM_PC-NUM_NIC_PC; pc++)
    if(neighbor[cn][pc] == dn)
    {*cpc=pc; return true;}

  return false;
}
void deterministic_route(int cn, int dn, int pc, int vc, int* dest_pc, int* dest_vc, flit_t *flit_ptr)
{
  // cn : current node  
  // dn : destination node  
  // cx, cy : x and y coordinate of the current node  
  // dx, dy : x and y coordinate of the destination node
  int cx, cy, dx, dy;
  int i, hx, hy;
  int credit[MAX_PC-MAX_NIC_PC], best_vc[MAX_PC-MAX_NIC_PC]; // number of available buffer
  int sn = flit_ptr->data.snode;
  int node = cn;
  int tmp_pc;

  get_best_credit(cn, credit, best_vc); // Check the maximum number of available buffer of VCs in a PC.
  
 //This is over ridden in stage1() in router.cpp 
  *dest_vc = vc;
  

  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  // Hybrid Topology Support
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  if(hybrid_topology == YES)
  {
    //Local to Local communication
    if(router_info[cn].type == LOCAL && cn == dn)
    {
      *dest_pc = flit_ptr->data.dest % concentration_degree + NUM_PC-NUM_NIC_PC;
      //printf("returning cn:%d dn:%d pc:%d\n",cn,dn,*dest_pc);
      return;
    }
    //Local to global communication
    else if(router_info[cn].type == LOCAL && cn != dn)
    {
      *dest_pc = 0;//flit_ptr->data.dest % concentration_degree + NUM_PC-NUM_NIC_PC;
      //printf("returning cn:%d dn:%d pc:%d\n",cn,dn,*dest_pc);
      return;
    }
    //global to local communication
    else if(router_info[cn].type == GLOBAL && is_neighbor(cn,dn,&tmp_pc) == true)
    {
      *dest_pc = tmp_pc;
      //if(tmp_pc != 4)
      //{printf("returning cn:%d dn:%d tmp_pc%d\n",cn,dn,tmp_pc);exit(1);}
      //printf("returning cn:%d dn:%d pc:%d\n",cn,dn,*dest_pc);
      return;
    }
    //global to global communication
    else if(router_info[cn].type == GLOBAL)
    {
      if(topology == MESH || topology == TORUS)
      {
        //first routers are local routers, offset the node addresses by number oflocal
        //routers so that we can correctly calculate grid address (row,col)
        cn -= NUM_PE/concentration_degree;
        //for destination node is the local router address so just convert to its
        //nearest global neighbor and then offset it by local routers to
        //calculate the correct grid address.
        dn = neighbor[dn][0] - NUM_PE/concentration_degree;
        //Now continue routing in global network
      }
      if(topology == FTREE)
      {
        cn -= NUM_PE/concentration_degree;
        dn = neighbor[dn][0] - NUM_PE/concentration_degree;
        //Now continue routing in global network
      }
    }
  }
  
  
  calc_coord(cn, &cx, &cy);
  calc_coord(dn, &dx, &dy);


  hx = MESH_NUM_COLS / 2;
  hy = MESH_NUM_ROWS / 2;

  // dx,cx here is direction in X and corresponds to col
  // dy,cy here is direction in Y and corresponds to row
  // counter intuitive please note
  
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  //1. Mesh
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  if(topology == MESH)
  {
    if     (dx  > cx) *dest_pc = RIGHT;
    else if(dx  < cx) *dest_pc = LEFT;
    else if(dy  > cy) *dest_pc = UP;
    else if(dy  < cy) *dest_pc = DOWN;
    else if(dn == cn) *dest_pc = THIS;
    if(concentration_degree > 1 && router_info[cn].type == FLAT  && dn == cn)
      *dest_pc = flit_ptr->data.dest % concentration_degree + THIS;
  }
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  //2. Torus
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  else if(topology == TORUS)
  {
    if     (dx  > cx) *dest_pc = (dx-cx <= hx)? RIGHT : LEFT ;
    else if(dx  < cx) *dest_pc = (cx-dx <  hx)? LEFT  : RIGHT;
    else if(dy  > cy) *dest_pc = (dy-cy <= hy)? UP    : DOWN ;
    else if(dy  < cy) *dest_pc = (cy-dy <  hy)? DOWN  : UP   ;
    else if(dn == cn) *dest_pc = THIS;
    if(concentration_degree > 1 && router_info[cn].type == FLAT && dn == cn)
      *dest_pc = flit_ptr->data.dest % concentration_degree + THIS;

  }
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  //3. Bus or Xbar (single router topology)
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  else if(topology == BUS  || topology == XBAR)
  {
    *dest_pc =  flit_ptr->data.dest;
  }
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  //4. Butterfly
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  else if(topology == BFLY)
  {
    if(verbose == YES)
      printf("Routing dn :%d cn:%d dest:%d\n", dn,cn,flit_ptr->data.dest);
    //Ejection at this node
    if(dn == cn)
    {
      //*dest_pc = (bfly.n - 1)*(bfly.k - 1) + (flit_ptr->data.dest % bfly.k) - 1;  
      *dest_pc = NUM_PC - NUM_NIC_PC + (flit_ptr->data.dest % bfly.k);  
      //printf("dest_pc:%d num pc%d\n",*dest_pc, NUM_PC);
    }
    else
    {
      // FIXME maximum n fly in butterfly allowed is 20
      int daddr[20], caddr[20], cn_temp=cn*bfly.k, dn_temp=flit_ptr->data.dest;

      for(i = bfly.n-1; i>=0 ; i--)
      {
        daddr[i] = dn_temp/(int)pow(bfly.k,i); 
        caddr[i] = cn_temp/(int)pow(bfly.k,i); 
        dn_temp = dn_temp%(int)pow(bfly.k,i);
        cn_temp = cn_temp%(int)pow(bfly.k,i);
        if(verbose == YES)
          printf("bit :%d [daddr/caddr] [%d/%d] \n",i,daddr[i],caddr[i]);
      }
      // Least dimension routing (DOR) Can be made to be more adpative routing
      // add code for checking which pc has least occupancy
      //FIXME supports at max 10 dimensions
      int dimconst[10]={0};
      for(i = 1; i <= bfly.n-1;  i++)
        dimconst[i] = (int)(floor(cn/pow(bfly.k,i-1))) % bfly.k; 
      for(i = 1; i <= bfly.n-1;  i++)
      {
        if(verbose == YES)
          printf("i:%d dimconst:%d\n",i,dimconst[i]);
        //dimconst[i] = (int)(floor(cn/pow(bfly.k,i-1))) % bfly.k; 
        if(daddr[i] != dimconst[i])
          if(daddr[i] != caddr[i]) 
            break;

      }
      if(verbose == YES)
        printf("Chose the dimesnion :%d to route\n",i);

      if(daddr[i] > dimconst[i])
        *dest_pc = (i-1)*(bfly.k-1) + daddr[i] - 1;
      else
        *dest_pc = (i-1)*(bfly.k-1) + daddr[i];
    }
  }
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  //5. Fat Tree
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  else if(topology == FTREE)
  {
    int offset=0;
    /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
    // Hybrid Topology Support
    /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
    if(hybrid_topology == YES)
      offset = NUM_PE/concentration_degree;

    if(dn == cn)
    {
     *dest_pc = flit_ptr->data.dest % concentration_degree + NUM_PC-NUM_NIC_PC;
    /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
    // Hybrid Topology Support
    /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
    if(hybrid_topology == YES)
      *dest_pc = neighbor_pc[flit_ptr->data.dnode][0];
    }
    else if(is_neighbor(cn+offset,dn+offset,&tmp_pc) == true)
    {
      *dest_pc = tmp_pc;
    }
    else
     *dest_pc = 0;
    //printf("returning cn:%d dn:%d pc:%d\n",cn+offset,dn+offset,*dest_pc);
  }

  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
  // VC allocation (FIXME not used currently over ridden in stage1() in
  // router.cpp
  /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/

  // As for now, use the same vc
  //*dest_vc = vc;
  //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  // Now, routing decision has been made. Set new direction(PC) and VC.
  // If no VCs have available buffer (best_vc[*dest_pc] == -1), use the same VC as before.
  if(*dest_pc >= (NUM_PC - NUM_NIC_PC))
    *dest_vc = 0;
  else
    *dest_vc = (best_vc[*dest_pc] != -1)? best_vc[*dest_pc] : vc;

  if(verbose == YES)
    printf("Routing dn :%d cn:%d dest:%d dest pc :%d dest vc:%d chosen\n", 
        dn,cn,flit_ptr->data.dest,*dest_pc,*dest_vc);
}
